docs/Binary tree reorganization hashing insertion.htm

   1 <HEAD>
   2 <TITLE>Binary tree reorganization hashing: insertion
   3 </TITLE>
   4 <BODY>
   5 <H2>
   6 <H3>
   7 <A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
   8 <A HREF="../../hbook.html">
   9 <IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4></A><BR>
  10 <A HREF="../../expand.html">
  11 <IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4></A><BR>
  12 <A HREF="../../search_a.html">
  13 <IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4></A><BR>
  14 <A HREF="311.ins.c.html"><IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4></A><BR>
  15 <A HREF="311c.srch.c.html">
  16 <IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4></A><BR>
  17 <BR></H2>
  18 <HR>
  19 <H2><B>Binary tree reorganization hashing: insertion
  20 </B></H2><BR>
  21 <CENTER>
  22 <TABLE BORDER>
  23 <TR>
  24 <TD COLSPAN = 1>
  25 <TD rowspan = 1>
  26 <TR><TD>
  27 <XMP>
  28      procedure insert( key : typekey; var r : dataarray );
  29      var i, inc, init, j : integer;
  30
  31           function SearchMove ( init, inc, level : integer ) : integer;
  32           {*** Find the first hole (empty location) at the given depth
  33                in the binary tree spanned by a key ***}
  34           label     999;
  35           var  i, inc1, j, k : integer;
  36           begin
  37           i := (init + inc*level) mod m;
  38           if empty(r[i]) or deleted(r[i]) then SearchMove := i
  39           else begin
  40                for j:=level-1 downto 0 do begin
  41                     i := (init + inc*j) mod m;
  42                     inc1 := increment( r[i].k );
  43                     k := SearchMove( (i+inc1) mod m, inc1, level-j-1 );
  44                     if k>-1 then begin
  45                          {*** A hole was found, move forward ***}
  46                          r[k] := r[i];
  47                          SearchMove := i;
  48                          goto 999  {*** return ***}
  49                          end
  50                     end;
  51                {*** Could not find hole ***}
  52                SearchMove := -1;
  53                end;
  54           999:
  55           end;
  56
  57      begin
  58      init := hashfunction( key );
  59      inc  := increment( key );
  60      i := 0;        j := -1;
  61      while (i<=n) and (j<0) and (n<m) do begin
  62           j := SearchMove( init, inc, i );
  63           i := i+1
  64           end;
  65      if j>-1 then begin
  66           {*** A hole was found, insert key ***}
  67           r[j].k := key;
  68           n := n+1
  69           end
  70      else Error     {*** table is full ***};
  71      end;
  72 </XMP></TD></TR></TABLE>
  73 <BR>
  74 <H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/3382.ins.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (3382.ins.p)  </H3></CENTER>
  75 <HR><H4>
  76 <IMG SRC="../../images/aw3.gif" align=left><H5><BR>
  77 &copy <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
  78 </H5></H4><HR>
  79 </BODY>